
public class BinarySearch {
    // 递归实现：arr必须是升序数组
    public static int searchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) return -1; // 目标不存在
        int mid = left + (right - left) / 2; // 避免溢出，等价于 (left+right)/2

        if (arr[mid] == target) return mid; // 找到目标，返回索引
        else if (arr[mid] > target) return searchRecursive(arr, target, left, mid - 1); // 左半区查找
        else return searchRecursive(arr, target, mid + 1, right); // 右半区查找
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        int index = searchRecursive(arr, target, 0, arr.length - 1);
        System.out.println(target + " 的索引：" + (index == -1 ? "不存在" : index)); // 输出：23 的索引：5
    }
}
/*public class MaximumSubarraySum {
    // 核心：计算跨左右区的最大和
    private static int crossMaxSum(int[] arr, int left, int mid, int right) {
        int leftMax = Integer.MIN_VALUE;
        int sum = 0;
        // 从mid向左遍历，找左半区最大后缀和
        for (int i = mid; i >= left; i--) {
            sum += arr[i];
            leftMax = Math.max(leftMax, sum);
        }

        int rightMax = Integer.MIN_VALUE;
        sum = 0;
        // 从mid+1向右遍历，找右半区最大前缀和
        for (int i = mid + 1; i <= right; i++) {
            sum += arr[i];
            rightMax = Math.max(rightMax, sum);
        }
        return leftMax + rightMax; // 跨区最大和 = 左后缀最大 + 右前缀最大
    }

    // 递归分治
    private static int maxSum(int[] arr, int left, int right) {
        if (left == right) return arr[left]; // 基线条件：只有一个元素

        int mid = left + (right - left) / 2;
        int leftMax = maxSum(arr, left, mid); // 左半区最大和
        int rightMax = maxSum(arr, mid + 1, right); // 右半区最大和
        int crossMax = crossMaxSum(arr, left, mid, right); // 跨区最大和

        return Math.max(Math.max(leftMax, rightMax), crossMax); // 取三者最大值
    }

    // 测试（LeetCode经典案例：[-2,1,-3,4,-1,2,1,-5,4]，最大和为6）
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("最大子序列和：" + maxSum(arr, 0, arr.length - 1)); // 输出：6
    }*/
//}